﻿using System;

namespace _3.埃氏筛
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("请输入要求素数的范围：");
            string numStr = Console.ReadLine();
            int num = Convert.ToInt32(numStr);
            double sqrtNum = Math.Sqrt(num);
            bool []NotPrime = new bool[num+1];
            for(int i = 2; i <= sqrtNum; ++i)
            {
                for (int j = 2*i; j <= num; j += i) NotPrime[j] = true;
            }

            Console.WriteLine("2到{0}的素数有：", num);
            for(int i = 2; i <= num; ++i)
            {
                if (!NotPrime[i]) Console.Write(i + " ");
            }

        }
    }
}
